Another O(n) solution use cycle sort:

def firstMissingPositive(self, nums: List[int]) -> int:
    i = 0
    n = len(nums)
    while i < n:
        j = nums[i] - 1
        # put num[i] to the correct place if nums[i] in the range [1, n]
        if 0 <= j < n and nums[i] != nums[j]:
            nums[i], nums[j] = nums[j], nums[i]
        else:
            i += 1
    # so far, all the integers that could find their own correct place 
    # have been put to the correct place, next thing is to find out the
    # place that occupied wrongly
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

Solution with a string of length of n is not O(1) space complexity, it's O(n)

The problem should specify that it is ok if you alter the existing array because to my surprise the LeetCode solution doesn't care about modifying the existing array.

Nice solution, but it's possible to do this in one pass, considering each value at most twice, and not destroying the contents of the array (though changing its order).

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        // We will partition the array into two sides, with one copy of each number
        // on the left, in order, as far as possible.
        // [1, 2, 3, 4, 5, ..., n][...(everything else, but not n+1)...].
        int i = 0, end = nums.size();
        // Call LeftPartition the interval [1, ..., i - 1]
        // Call RightPartition the interval [nums[end], nums[nums.size() - 1]].
        // Initially, both are empty.
        // At the end, when "i" and "end" meet, call the results FinalLeftPartition and FinalRightPartition.
        // Then the answer to the problem is 1 + size(FinalLeftPartition).
        //
        // We build those intervals in-place, by swapping elements when necessary, and updating i and end.
        while (i != end) {
            int val = nums[i];
            if (val == 1 + i) // Number is in the right place. We may consider it part of LeftPartition, and advance i.
                ++i;
            else if (
                val > end // If this should go in FinalLeftPartition, then that would overlap with FinalRightPartition.
                || val <= 0 // The number is negative, it cannot possibly belong in FinalLeftPartition.
                || nums[val - 1] == val // This is a duplicate. It doesn't belong in FinalLeftPartition.
                    // How can we get away with checking just this one spot for a duplicate?
                    // See the next "else" branch -- we always put values into this exact spot.
            ) {
                // If any of the above statements is true, this value doesn't need to be in FinalLeftPartition.
                // So we may put it in the right partition,
                // and advance "end".
                swap(nums[i], nums[--end]);
                // Now nums[i] has some new value that we haven't considered before, so
                // leave "i" as is and go back to the top of the loop.
            } else {
                // We don't yet know whether val should be in
                // FinalLeftPartition or FinalRightPartition, so put it in neither.
                // In order to consider another value, place val so that it matches its own index;
                // that is, place it where it will be if indeed it ends up in FinalLeftPartition,
                // and next consider the element there.
                swap(nums[i], nums[val - 1]);
                // We learned nothing new about what elements will be in FinalLeftPartition or FinalRightPartition,
                // and nums[i] has the previous value of nums[val - i], which we haven't dealt with yet,
                // so continue the loop without advancing either pointer.
                // But we did make useful progress in this branch: now in the future, if we see the same "val"
                // again, we will know it's a duplicate, because of the "nums[val - 1] == val" check above!
            }
        }
        return i + 1;
    }
};

One could get rid of all numbers larger than n as well, since the first missing positive is for sure smaller or equal to n + 1

This isn't obvious and could use some more explanation.

I find solutions that just state something without proving it to be especially annoying.

I tried to give an explanation here:

https://leetcode.com/problems/first-missing-positive/discuss/319270/Explanation-of-crucial-observation-needed-to-deduce-algorithm

This doesn't really count as O(1) because it relies on destructively modifying the input, and in almost any real life use case, you never want your functions to modify the input data.

we can apply cyclic replacement which cost O(n) to swap and put all numbers in their correct positions in array

class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i ++){
            int curr = nums[i];
            // curr-1 is the next index to swap and must be inside bound
            while (curr-1 >= 0 && curr-1 < nums.length && nums[curr - 1] != curr){
                int temp = nums[curr - 1];
                nums[curr - 1] = curr;
                curr = temp;
            }
        }
        for (int i = 0; i < nums.length; i ++){
            if (nums[i] != i + 1) return i + 1;
        }
        return nums.length + 1;
    }
}    

Should the following statement:
If array contains only one element and it's not 1, the answer is 2.
be:
If array contains only one element and it's 1, the answer is 2.
?

just use a heap..

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        heapq.heapify(nums)
        num = 1
        for i in range(len(nums)):
            x = heapq.heappop(nums)
            if (x > 0 and x==num):
                num+=1
        return num

And ArrayIndexOutOfBoundsException while processing {1,3,3};

Should:
else if (nums[a] > 0)
nums[a] *= -1;
be changed to:
else if (a != n && nums[a] > 0)
nums[a] *= -1;
?